﻿//【初阶】20.stack和queue(1)

//【头文件包含】
//C++的主要头文件
#include<iostream>//c++的输入输出流
using std::cout, std::endl, std::cin;

#include<stack>
#include<queue>
#include<string>
#include<deque>;
using std::deque;
using std::stack;
using std::queue;
using std::string;
//C的主要头文件
//#include<stdio.h>
//#include<stdlib.h>
//#include<assert.h>
//#include<string.h> 
#include<vector>;
using std::vector;
#include"stack.h"
#include"queue.h"

#include<algorithm>
#include<time.h>



//【命名空间】

//【结构体声明】【类声明】
class Solution {
public:
    /*模拟实现字符串数字转换为整形*/int sti(string s)
    {
        int flage = 1;
        int i = 0;
        int ret = 0;
        if (s[i] == '-')
        {
            ++i;
            ret = s[i] - '0';
            flage = -1;
            ++i;
        }
        else {
            ret = s[i] - '0';
            ++i;
        }

        for (; i < s.size(); ++i)
        {
            ret *= 10;
            ret += s[i] - '0';
        }
        return ret * flage;
    }
    /*逆波兰表达式求值*/int evalRPN(vector<string>& tokens)
    {
        stack<int> st;
        for (auto& str : tokens)
        {
            if (str == "+" || str == "-" || str == "*" || str == "/")
            {
                int rt = st.top();
                st.pop();
                int lt = st.top();
                st.pop();
                switch (str[0])
                {
                case '+':
                    st.push(lt + rt);
                    break;
                case '-':
                    st.push(lt - rt);
                    break;
                case '*':
                    st.push(lt * rt);
                    break;
                case '/':
                    st.push(lt / rt);
                    break;
                }
            }
            else
            {
                st.push(sti(str));
                //st.push(stoi(str));//str自带的字符串转整形
            }
        }
        return st.top();
    }
};


//【函数声明】
void Test1();void Test2();void Test3(); 

//【主函数】
int main()
{
	
	Test1();
	Test2();
	Test3();
    
	cout << "****主函数结束****" << endl;
	return 0;
}
/*测试用例*/void Test1()
{
	cout << "****测试用例开始****"<< endl;
    myspace::test_stack1();
    myspace::test_queue1();
	

	cout << "****测试用例结束****" << endl << endl;
}
/*测试用例*/void Test2()
{
	cout << "****测试用例开始****" << endl;
    deque<int> d;
    vector<int> v;
    const int n = 100000;
    srand(time(0));
    for (size_t i = 0; i < n; ++i)
    {
        int x = rand();
        d.push_back(x);

        v.push_back(x);
    }
    size_t begin1 = clock();
    sort(d.begin(), d.end());
    size_t end1 = clock();
    cout << end1 - begin1 << endl;
    size_t begin2 = clock();
    sort(v.begin(), v.end());
    size_t end2 = clock();
    cout << end2 - begin2 << endl;
	cout << "****测试用例结束****" << endl<<endl;
}

/*测试用例*/void Test3()
{
	cout << "****测试用例开始****" << endl;
	
	cout << "****测试用例结束****" << endl << endl;
}



//【笔记】
//【初阶】20.stack和queue(1)
//适配器
    // 利用适配器可以将容器适配转换为需要的新的类，技巧：利用模版函数
//适配器：stl的栈，  支持 vector和list
//适配器:stl的队列，只支持list
// stl中的栈和队列都是利用容器适配封装转换出来的并非原生实现的，本质上是一种复用 
//双端队列deque
    //模版
        //stl的queue 模版是template <class T, class Container = deque<T> > class queue;
        //其中deque为双端队列template < class T, class Alloc = allocator<T> > class deque;
    //优缺点
        //【优点】deque即支持双端进出，同时也支持迭代器和随机访问，融合了vector和list的功能
        //【缺点】在进行随机访问和排序等的实现时性能相较vector不足
    //实现原理
        // 避免增容带来的性能影响
            // 在开辟空间时采用一次开辟一块小的buffer（小段的数组）存满后不增容再开辟一块小数组
        // 头插头删挪动数据的效率
            // 在删除数据时不需要挪动数据直接删除位置元素
            // 在头插时在头部再开一个数组插数据
        // 多个数组间的连接和管理
            // 利用中控映射：即存在一个指针数组用于管理每个buffer数组
        //operator[]随机访问
            //首先计算访问的第i个数组在哪个buffer，再进行访问
            // 当元素数量过大时，效率和性能逐渐降低
        //迭代器结构组成
            // 当前buffer的头尾first、last
            // 迭代器在当前数组所处位置cur
            // 迭代器所处的当前数组在中控映射的指针数组所处的位置node 
        //下节课继续...




